package com.ohc.小码哥.第二季.排序;

/**
 * @Author 欧皓辰
 * @Date 2021/12/22 23:04
 * @Version 1.0
 */
public class BinarySearch {
    /**
     * 通过二分查找，找出这个值对应的索引
     *
     * @param array
     * @param v
     * @return
     */
    public static int indexOf(int[] array, int v) {
        if (array == null || array.length < 2) return -1;
        int begin = 0;
        int end = array.length - 1;
        while (begin < end) {
            int mid = (begin + end) >> 1;
            if (v < array[mid]) {
                end = mid;
            } else if (v > array[mid]) {
                begin = mid + 1;   // 这里+或不+都可以
            } else {
                return mid;
            }
        }
        return -1;
    }


    /**
     * 查找v在有序数组array中待插入位置
     *
     * @param array
     * @param v
     * @return
     */
    public static int search(int[] array, int v) {
        if (array == null || array.length < 2) return -1;
        int begin = 0;
        int end = array.length;   // 左闭右开
        while (begin < end) {
            int mid = (begin + end) >> 1;
            if (v < array[mid]) {
                end = mid;
            } else {
                begin = mid + 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {0, 1, 2, 3, 4, 5};
        int i = indexOf(arr, 2);
        System.out.println("i = " + i);
    }
}
